Information Centric Networking (ICN) is an alternative approach to the architecture of computer networks. Its founding principle is that a communication network should allow a user to focus on the needed data, rather than having to reference a specific, physical location where that data is to be retrieved from. This stems from the fact that the vast majority of current Internet usage (90%) consists of data being disseminated from a source to a number of users.
ICN has introduced a new networking model, where the communication is centered on named-data rather than host address. Indeed, in ICN every data packet is identified, addressed and retrieved by its unique name instead of its physical location.
Among the several ICN architectures that have been proposed in recent years, the best known example is represented by the Content Centric Networking (CCN), also known as Named Data Networking (NDN). While ICN architectures generally differ in a number of choices (e.g., flat vs hierarchical naming strategy, routing and forwarding strategies, granularity of minimum addressable entity, etc.), they however generally have common points—such as featuring caching functionalities as primitive in the architecture. Since a common terminology that encompasses all ICN proposals is currently missing, in this context we adopt the CCN lingo for the sake of clarity, but we point out that our approach is applicable to a greater extent.
Thus, in ICN all network nodes (routers) potentially store a content (which is split in “chunks”, i.e. elementary fragments of data with a given size, in other words “blocks”) that they forward to serve future requests for the same content. Therefore, it is possible to equip network nodes with enhanced storage capabilities such as caches/buffer memories. Indeed, storage resources can be used to maintain temporary content replicas spread through the network for a period of time ranging from minutes to hours or days. The availability of different replicas depends on several factors, such as content popularity, cache replacement policies, and is impacted by the request forwarding policy. The term “request forwarding policy” refers here broadly and as non-limitative, to ways/rules to manage the forwarding of a content request within a network comprising nodes. In fact, request forwarding policy plays an important role in providing better end-users performance (ex: data delivery time) and reducing the amount of data transferred in a network, i.e. providing a lower network load.
Servers in ICN announce the set of content items they can serve by means of routing protocols, i.e. prefixes of permanently stored items. Network nodes receiving these announcements build their forwarding/routing tables accordingly. For instance network nodes store in their routing tables, the shortest paths in terms of delay towards a permanent copy of a file. Chunks of a file are then requested by a receiver, through Interest packets that are forwarded by network nodes towards servers storing permanent copies of the requested chunks.
Interest packet here is a packet type, referring to interest/request about content item/file. Another packet type referred in this document is Data packet, corresponding to data transmitted in response to an interest/request of content (i.e. Interest packet). Indeed, a Data packet may be a chunk of a content item/file. Interest packet leaves traces that a matching chunk (i.e. Data packet) can follow via reverse path, to reach back the original requester. A matching chunk can be found in every node caching a temporary copy or at the server where the permanent copy is stored. In fact, one Interest packet permits to retrieve one Data packet. Hence, a sequence of Interest packets permits to retrieve a sequence of Data packets, i.e. for instance the chunks of a large piece of content such as a video file.
On the algorithmic side, a ICN node not only performs forwarding functions (similarly to an IP router) but additionally implements caching decision and replacement policies (unlike in IP). As represented by FIG. 1, at high level a cache network can be modeled as a triple (F, D, R), where:                F represents the forwarding policy, determining the next hop for each content request, whereas content items travel back along breadcrumbs left by the requests;        a meta-caching algorithm D let nodes decide whether to store any new content item passing by;        a replacement algorithm R selects, in case of positive decision in the previous step, which cache element should be replaced to make room for the new one.        
Given the pervasiveness of caches in ICN, meta-caching is considered a crucial element to differentiate content of individual caches. Forwarding is instead essential to extend the reach beyond caches that lay on the path toward the repository, possibly reaching off path copies.
Yet, while ICN performances are dependent on the triple F, D, R, research has so far limitedly considered a single of the above aspect in isolation. More specifically, work focusing on F aims at implementing policies to efficiently reach off-path caches, and assumes that newly arriving content is always cached generally referred to as Leave a Copy Everywhere (LCE) in meta-caching terms.
Work focusing on D instead aims at implementing policies to reduce cache redundancy, and assumes that requests are forwarded according to Shortest Path Routing (SPR). Most importantly, a debate has been recently ignited around the usefulness of ubiquitous caching. In particular, very recent work shows that the most of the caching gain is attainable by simply (and painlessly) caching at the edge of the network.
A crucial point is still missing: the interaction of the above policies concurs in determining the global ICN performance.
While an ideal forwarding policy F (that achieves optimal forwarding decisions) has been correctly select, the implicit subsequent selection of the D, R pair (and especially of the meta-caching policy D) yields to significant underestimation of the achievable ICN performances.
Hence, a first innovation consist in the jointly considering (and solving) both problems.
A second, more crucial innovation, consist in proposing practically implementable schemes that achieve performance of optimal schemes. These ideal schemes, known in the literature (see S. K. Fayazbakhsh, Y. Lin, A. Tootoonchian, A. Ghodsi, T. Koponen, B. M. Maggs, K. Ng, V. Sekar, and S. Shenker. “Less pain, most of the gain: Incrementally deployable”. In ACM SIGCOMM, 2013) as ideal Nearest Replica Routing (iNRR) have desirable properties (i.e., to attain the closest cached replica) yet they are hard to implement in a general network setting—as the closest replica cannot be advertised in the control plane, whereas ICN data plane lookups trigger unnecessary cache eviction, yielding to “cache pollution” (i.e., unnecessary content eviction when the new data is stored at multiple hops in the path) and letting the system operate in an inefficient point.
There is a need for a method allowing to explore the network and to find the closest replica, while eliminating problems arising from cache pollution.